package top100;

import java.util.LinkedList;

/**
 * @author Godc
 * @description
 */
public class Trap {
    public static void main(String[] args) {
        TrapSolution s = new TrapSolution();
        System.out.println(s.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }
}
class TrapSolution {
    public int trap(int[] height) {
        LinkedList<Integer> stack = new LinkedList();
        stack.push(0);
        int res = 0;
        for(int i = 1;i<height.length;i++){
            if(height[stack.peek()]>height[i]) stack.push(i);
            else if(height[stack.peek()]==height[i]){
                stack.pop();
                stack.push(i);
            }else{
                while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
                    int mid = stack.pop();
                    if(!stack.isEmpty()){
                        int left = height[stack.peek()];
                        int right = height[i];
                        int w = i-stack.peek()-1;
                        int h = Math.min(left,right)-height[mid];
                         res+=(w*h);
                    }
                }
                stack.push(i);
            }
        }
        return res;

    }
}